#include <stdio.h>
#include <stdlib.h>

#define debug(...)  \
  printf( __VA_ARGS__); printf( "\n" )

#define info(...)  printf(__VA_ARGS__); printf( "\n" )
#define error(...)  do {\
                          printf(__VA_ARGS__);\
                          exit(-1);\
                      }while(0);

typedef struct _node node;
struct _node{
  int key;
  node* parent;
  node* left;
  node* right;
};

node* insert(node *root, int key);
void inorder_traverse(node* root);
node* new_node(int key);
node* tree_min( node *root );
node* tree_max( node *root );
node* inorder_predecessor( node *root );
node* search_node( node *root, int key );
int height( node* root );

void 
main () {
  node *root = NULL;
  root = insert( root, 15);
  insert( root, 6 );
  insert( root, 18 );
  insert( root, 3 );
  insert( root, 7 );
  insert( root, 2);
  insert( root, 4 );
  insert( root, 13 );
  insert( root, 9 );
  insert( root, 17 );
  insert( root, 20 );
  inorder_traverse( root );
  info( "Min element %d", tree_min(root)->key );
  info( "Max element %d", tree_max(root)->key );
	info( "Inorder predecessor of 17 is %d", 
				inorder_predecessor( search_node( root, 17 ) )->key);
	info( "Inorder predecessor of 6 is %d", 
				inorder_predecessor( search_node( root, 6 ) )->key);
	info( "Inorder predecessor of 13 is %d", 
				inorder_predecessor( search_node( root, 13 ) )->key);
  info( "Height of tree %d", height(root) );
}

node*
insert(node *root, int key) {
  if ( root ) {
    if ( key < root->key ) {
        root->left = insert( root->left, key );
        root->left->parent = root;
    }
    else {
        root->right = insert( root->right, key );
        root->right->parent = root;
    }
  }
  else 
    return new_node( key );
  
  return root;
}
void
inorder_traverse(node* root) {
  if ( root ) {
    inorder_traverse(root->left);
    printf("%d ", root->key);
    inorder_traverse(root->right);
  }
}

node*
new_node( int key ) {
  node *new = malloc( sizeof( node ) );
  new->key = key;
  new->left = NULL;
  new->right = NULL;
  new->parent = NULL;
  return new;
}
/** 
 * Recursively find minimum element in Binary Search Tree.
 * @param[in] root node of BST 
 * @retval node whose key value is minimum in BST.
 * */
node*
tree_min( node *root ) {
  if ( root->left == NULL )
    return root;
  else 
    return tree_min( root->left );
}
/**
 * Iteratively find maximum element 
 * @param[in] root node of BST
 * @retval node whose key value is Maximum in BST.
 * */
node* 
tree_max( node *root ) {
	node *min = root;
	while ( min->right )
		min = min->right;
	return min;
}
/** 
 * Finds inorder predecessor of a random node. 
 * @param[in] root a random BST node.
 * @retval inorder predecessor node. 
 * */
node* 
inorder_predecessor( node *root ) {
	node *predecessor;
	/* Case 1. Node has left child then rightmost node will be the required
	 * node.
	 * Case 2. Node has no left child then trace the parent link to find the
	 * the node who is right child of its parent, it also covers the current
	 * node. */
	if ( root ) {
		if ( root->left )
			return tree_max( root->left );
		else {
			predecessor = root->parent;
			/* Iterate till root is not right child of its parent. */
			while ( predecessor != NULL && root == predecessor->left ) {
				root = predecessor;
				predecessor = predecessor->parent;
			}
			return predecessor;
		}
	}
	else 
		return NULL;
}
/**
 * Searches a node in BST.
 * @param[in] root Root node of tree.
 * @param[in] key Key value of node.
 * @retval Tree node.
 */
node* 
search_node( node *root, int key ) {
	if ( root ) {
		if ( root->key == key )
			return root;
		else {
			if ( key < root->key )
				return search_node( root->left, key );
			else
				return search_node( root->right, key );
		}
	}
	else 
		return NULL;
}
/**
 * Calculates height of a tree.
 * @param[in] Root node of tree.
 * @retval height of the tree.
 */
int 
height( node* root )
{
  if ( root == NULL )
    return 0;
  else {
    //debug( "current node %d", root->key );
    /* compute the height of each subtree */
    int lheight = height( root->left );
    int rheight = height( root->right );
    //debug( "lheight %d, rheight %d", lheight, rheight );
    //debug( "processed node %d", root->key );

    /* use the larger one */
    if ( lheight > rheight )
      return( lheight+1 );
    else 
      return( rheight+1 );
  }
} 
